//希尔排序[仅适用于顺序表，不适用于链表]
/*
    先将待排序表分割成若干形如L[i, i+d, i+2d, ……， i+kd]的"特殊"子表，对各个子表分别进行直接插入排序。缩小增量(步长)d，重复上述过程，知道d=1为止。
*/
/*
    不稳定
    平均时间复杂度O(n^1.3)，最坏时间复杂度O(n^2);
    空间复杂度O(1);
*/

#include <iostream>

using namespace std;

void ShellSort(int A[], int n) //希尔排序(默认升序)
{
    int i, j, temp; //temp:插入操作的暂存单元
    int step;   //步长
    for (step = n/2; step >= 1; step /= 2)  //步长变化(初始值为n/2)
        for (i = step; i < n; ++i)  //对当前步长情况下对各个子表进行直接插入排序
            if (A[i] < A[i-step])   //如果发现A[i]需要调整位置
            {
                temp = A[i];    //把A[i]暂存在temp中
                for (j = i - step; j >= 0 && A[j] > temp; j -= step)  //检查当前子表中所有前面已排好序的元素
                    A[j + step] = A[j]; //所有大于temp的元素都向后挪位，空出A[i]的插入位置
                A[j + step] = temp;     //把temp(A[i])插入到大于等于前驱的位置上
            }
    return;
}



//测试代码
int main()
{
    int A[100] = {2, 4, 3, 7, 9, 1, 6, 5, 8};
    ShellSort(A, 9);
    for (int i = 0; i < 9; ++i)
        cout << A[i] << ' ';
    return 0;
}